/*
 * LCS.cpp
 *
 *  Copyright   : Copyright © 2011 Binda&Aeolus; All Rights Reserved
 *  Created on: 2011-3-6
 *  Author      :洪春晓
 */

#include "LCS.h"
#include <iostream>
#include<vector>
using std::vector;

namespace com_hcx {
	void LCS::LCSLength(int x_len,int y_len,char *X,char *Y,int longest_len[MAXLEN][MAXLEN])
	{
		int i,j;
		for(i=1 ; i!=x_len+1; i++ )
			longest_len[i][0]=0;
		for(j=1;j!=y_len+1; j++)
			longest_len[0][j] = 0;
		for(i=1; i!=x_len+1; i++)
			for(j=1; j!=y_len+1; j++)
			{
				if(X[i] == Y[j] )
				{
					longest_len[i][j] = longest_len[i-1][j-1]+1;
				}
				else if(longest_len[i-1][j] >= longest_len[i][j-1])
				{
					longest_len[i][j] = longest_len[i-1][j];
				}
				else
				{
					longest_len[i][j] = longest_len[i][j-1];
				}
			}
	}

	void LCS::getLCS(int i,int j,char*X,char*Y,int longest_len[MAXLEN][MAXLEN], vector<char> &lcs_data)
	{

			if(i==0 || j==0)
				return ;
			if(X[i]==Y[j])//longest_len[i][j] == longest_len[i-1][j-1]+1)
			{
				getLCS(i-1,j-1,X,Y,longest_len,lcs_data);
				std::cout<<X[i]<<"-"<<i<<" ";
				lcs_data.push_back(X[i]);
			}
			else if(longest_len[i][j] == longest_len[i-1][j])
			{
				getLCS(i-1,j,X,Y,longest_len,lcs_data);
			}
			else if(longest_len[i][j] == longest_len[i][j-1])
				getLCS(i,j-1,X,Y,longest_len,lcs_data);
	}
}
